package com.maishi.programmer.jainzhioffer;


/**
 * Created by brossdong on 2018/4/14.
 * 一个整型数组里除了两个数字之外，其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。
 * 如果a、b两个值不相同，则异或结果为1。如果a、b两个值相同，异或结果为0。
 */
public class TestProblem56 {

    public void FindNumsAppearOnce(int [] array,int num1[] , int num2[]) {
        int result = 0;
        if (array == null || array.length < 2) return;
        for (int i = 0; i < array.length; i++) {
            result ^= array[i];
        }
        int index = findFirst1(result);
        for(int i = 0; i < array.length; ++i){
            if(isBit1(array[i], index)){
                num1[0] ^= array[i];
            }else{
                num2[0] ^= array[i];
            }
        }
    }
    private int findFirst1(int bitResult){
        int index = 0;
        while(((bitResult & 1) == 0) && index < 32){
            bitResult >>= 1;
            index++;
        }
        return index;
    }

    private boolean isBit1(int target, int index){
        return ((target >> index) & 1) == 1;
    }
    /*public void FindNumsAppearOnce(int [] array,int num1[] , int num2[]) {
        ArrayList<Integer>list=new ArrayList<Integer>();
        for(int i=0;i<array.length;i++)
        {
            if(!list.contains(array[i]))
                list.add(array[i]);
            else
                list.remove(new Integer(array[i]));
        }
        if(list.size()>1)
        {
            num1[0]=list.get(0);
            num2[0]=list.get(1);
        }
    }*/

}

